package top.minuy.structure.graph.representations.table;

import java.io.File;
import java.io.IOException;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

/**
 * 带权图
 * 正式在后面的例子中使用的图的表示类 简单图
 * 使用基于红黑树的邻接表实现
 * V0.2
 * 带方向
 *
 * @author Minuy
 * @time 0:15
 * @date 2021/11/27
 */
public class WeightedGraph implements Cloneable {
    private int V; // 顶点个数
    private int E; // 边的条数
    private TreeMap<Integer, Integer>[] adj; // 邻接矩阵
    private boolean isDirected;
    // private int[] indegrees, outdegrees; // 出度，入度

    /**
     * 构造函数，构造一个图
     *
     * @param fileName 加载的文件名
     * @author Minuy
     * @date 2021/11/15 22:29
     */
    public WeightedGraph(String fileName) {
        this(fileName, false);
    }

    public WeightedGraph(String fileName, boolean isDirected) {

        this.isDirected = isDirected;

        File file = new File(fileName);

        // 这种语法可以不用手动关闭输入流
        try (Scanner scanner = new Scanner(file)) {
            V = scanner.nextInt(); // 读入顶点数量
            if (0 > V) {
                // 顶点数量 必须是非负数的
                throw new IllegalArgumentException("V must be non-negative.");
            }
            // 创建邻接矩阵
            adj = new TreeMap[V];
            for (int i = 0; i < V; i++) {
                adj[i] = new TreeMap<Integer, Integer>();
            }

//            if (isDirected()) { // 有向图开始维护度
//                indegrees = new int[V];
//                outdegrees = new int[V];
//            }

            E = scanner.nextInt(); // 读入边的数量
            if (0 > E) {
                // 边数量 必须是非负数的
                throw new IllegalArgumentException("E must be non-negative.");
            }
            for (int i = 0; i < E; i++) {
                int a = scanner.nextInt(); // 读入第一个顶点
                validateVertex(a);
                int b = scanner.nextInt(); // 读入第二个顶点
                validateVertex(b);
                int weight = scanner.nextInt(); // 读入权值

                if (a == b) {
                    // 自环，不允许出现在简单图中
                    throw new IllegalArgumentException("Self Loop is Detected!");
                }
                if (adj[a].containsKey(b)) {
                    // 平行边，不允许出现在简单图中
                    // 若其他地方需要用到平行边，一般我们保留最小的那个平行边的权值，
                    // 也可当做没有平行边来处理
                    throw new IllegalArgumentException("Parallel Edges are Detected!");
                }

                adj[a].put(b, weight); // 连接两个顶点
                if (isDirected()) {// 有向图维护度
//                    indegrees[b]++;
//                    outdegrees[a]++;
                } else {
                    adj[b].put(a, weight); // 无向图的表示是两边都相连的
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * 验证顶点序号的合法性
     *
     * @param v 顶点值
     * @author Minuy
     * @date 2021/11/15 17:26
     */
    public void validateVertex(int v) {
        if (v < 0 || v >= V) {
            throw new IllegalArgumentException("Vertex " + v + " is valid.");
        }
    }

    /**
     * 只读，边的数量
     *
     * @return int 边的数量
     * @author Minuy
     * @date 2021/11/15 17:35
     */
    public int E() {
        return E;
    }

    /**
     * 只读，顶点的数量
     *
     * @return int 顶点的数量
     * @author Minuy
     * @date 2021/11/15 17:35
     */
    public int V() {
        return V;
    }

    /**
     * 验证两个顶点之间是否有变
     *
     * @param v 顶点1的序号
     * @param w 顶点2的序号
     * @return boolean 有无边
     * @author Minuy
     * @date 2021/11/15 17:38
     */
    public boolean hasEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        return adj[v].containsKey(w);
    }

    /**
     * 返回与顶点v相邻的所有顶点
     *
     * @param v 顶点v
     * @return Array<Integer> 与顶点v相邻的所有顶点
     * @author Minuy
     * @date 2021/11/15 19:55
     */
    public Iterable<Integer> adj(int v) {
        validateVertex(v);
        return adj[v].keySet();
    }

    /**
     * 获取一条边的权值
     *
     * @param v 边的一端顶点
     * @param w 边的另一端顶点
     * @return int 这条边的权值
     * @author Minuy
     * @date 2021/11/25 9:31
     */
    public int getWeight(int v, int w) {
        if (hasEdge(v, w)) {
            return adj[v].get(w);
        }
        throw new IllegalArgumentException(String.format("Not has edge %d-%d.", v, w));
    }

    /**
     * 获取顶点v的度
     *
     * @param v 顶点v
     * @return int 顶点v的度
     * @author Minuy
     * @date 2021/11/15 17:46
     */
    public int degree(int v) {
        // TODO 对于有向图的度，分为出度和入度
        if (isDirected()) {
            throw new RuntimeException("The degree only works in directed graph.");
        }
        validateVertex(v);
        return adj[v].size();
    }


    /**
     * 入度
     *
     * @param v 顶点v
     * @return int 入度
     * @author Minuy
     * @date 2021/11/27 10:05
     */
    public int indegree(int v) {
        if (!isDirected()) {
            throw new RuntimeException("The indegree only works in directed graph.");
        }

        validateVertex(v);

        int ind = 0;
        for (int w = 0; w < V(); w++) {
            for (int x : adj(w)) {
                if (x == v) {
                    ind++;
                }
            }
        }
        return ind;

//        validateVertex(v);
//        return indegrees[v];
    }

    /**
     * 出度
     *
     * @param v 顶点v
     * @return int 出度
     * @author Minuy
     * @date 2021/11/27 10:05
     */
    public int outdegree(int v) {
        if (!isDirected()) {
            throw new RuntimeException("The outdegree only works in directed graph.");
        }
        validateVertex(v);
        return adj[v].size();
    }

    /**
     * 删除一条边
     *
     * @param v 顶点1
     * @param w 顶点2
     * @author Minuy
     * @date 2021/11/24 21:58
     */
    public void removeEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);

        if (adj[v].containsKey(w)) {
            E--;

//            if (isDirected()){
//                outdegrees[v]--;
//                indegrees[w]--;
//            }


            adj[v].remove(w); // 删除边，不存在不会报错

            if (!isDirected()) { // 如果无向才删除“平行边”
                adj[w].remove(v);
            }
        }
    }


    /**
     * 倒图， 针对于有向图
     *
     * @return WeightedGraph 倒图
     * @author Minuy
     * @date 2021/11/27 17:15
     */
    public WeightedGraph reverse() {

        if (!this.isDirected()) {
            throw new RuntimeException("The reverse only works in directed graph.");
        }

        try {
            WeightedGraph g = (WeightedGraph) super.clone();
            g.V = this.V;
            g.E = this.E;
            g.adj = new TreeMap[V];
            g.isDirected = this.isDirected();
            for (int v = 0; v < g.adj.length; v++) {
                g.adj[v] = new TreeMap<Integer, Integer>();
            }

            for (int v = 0; v < g.adj.length; v++) {
                for (Map.Entry<Integer, Integer> entry : this.adj[v].entrySet()) {
                    g.adj[entry.getKey()].put(v, entry.getValue());
                }
            }

            return g;
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return null;
    }


    /**
     * 深复制
     *
     * @return Graph 返回一个图
     * @author Minuy
     * @date 2021/11/24 22:05
     */
    @Override
    public WeightedGraph clone() {
        try {
            WeightedGraph g = (WeightedGraph) super.clone();
            g.V = this.V;
            g.E = this.E;
            g.adj = new TreeMap[V];
            g.isDirected = this.isDirected();
            for (int v = 0; v < g.adj.length; v++) {
                g.adj[v] = new TreeMap<Integer, Integer>();
                for (Map.Entry<Integer, Integer> entry : this.adj[v].entrySet()) {
                    g.adj[v].put(entry.getKey(), entry.getValue());
                }
            }
            return g;
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return null;
    }

    /**
     * 查询图是有向的还是无向的
     *
     * @return boolean 图的方向性
     * @author Minuy
     * @date 2021/11/27 9:08
     */
    public boolean isDirected() {
        return isDirected;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V = %d, E = %d, isDirected = %s\n", V, E, isDirected));
        for (int v = 0; v < V; v++) {
            sb.append(String.format("%d : ", v));
            int i = 0;
            for (Map.Entry<Integer, Integer> entry : adj[v].entrySet()) {
                sb.append(String.format("{%d:%d}", entry.getKey(), entry.getValue()));
                if (i != adj[v].size() - 1) {
                    sb.append(", ");
                }
                i++;
            }
            sb.append("\n");
        }
        return sb.toString();
    }
}
